package com.wanjl._04_算术表达式的转换及求值;

import java.util.*;

/**
 * @author WanJl
 * @version 1.0
 * @title Main
 * @description
 * @create 2023/12/15 23:12
 */
public class Main {
    /**
     * 中缀表达式转换为后缀表达式
     *
     * @param infix 中缀表达式字符串
     * @return 后缀表达式字符串
     */
    public static String infix2postfix(String infix) {
        //创建集合，模拟栈结构
        LinkedList<Character> list = new LinkedList<>();
        //将字符串转换为字符数组
        char[] chars = infix.toCharArray();

        //创建可变长度字符串对象，用来存储后缀表达式
        StringBuilder postfix = new StringBuilder();
        //循环遍历字符数组
        for (int i = 0; i < chars.length; i++) {
            //如果字符是数字
            if (Character.isDigit(chars[i])) {
                try {
                    //如果没有循环到最后一位时
                    if (i != chars.length - 1) {
                        //判断下一个字符是否是数字，如果不是数字
                        if (!Character.isDigit(chars[i + 1])) {
                            //追加字符
                            postfix.append(chars[i]);
                            //追加空格
                            postfix.append(" ");
                        } else {
                            //追加字符
                            postfix.append(chars[i]);
                        }
                    } else { //如果循环到最后一位时
                        //追加字符
                        postfix.append(chars[i] + " ");
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            } else {//如果不是
                //判断栈是否为空
                if (list.isEmpty()) {
                    //为空则直接将符号入栈
                    list.push(chars[i]);
                    //如果符号是(
                } else if (chars[i] == '(') {
                    //则直接将符号入栈
                    list.push(chars[i]);
                    //如果符号是)。
                } else if (chars[i] == ')' && list.peekFirst() != null) {
                    //则判断当前栈顶元素是否为(，如果不是
                    while (list.peekFirst() != '(') {
                        //则将元素出栈，并追加到后缀表达式
                        postfix.append(list.pop());
                        postfix.append(" ");
                    }
                    //最后将左括号出栈
                    list.pop();
                } else {
                    //判断运算符的优先级，如果当前元素的优先级小于或等于栈顶元素符号
                    while (prio(chars[i]) <= prio(list.peekFirst())) {
                        //则将栈顶元素出栈并追加到后缀表达式
                        postfix.append(list.pop() + " ");
                        //如果是空则break
                        if (list.isEmpty()) {
                            break;
                        }
                    }
                    //然后将当前元素入栈
                    list.push(chars[i]);
                }
            }
        }
        //当循环遍历所有字符后，判断栈是否为空，如果不为空
        while (!list.isEmpty()) {
            //则将元素依次出栈，并追加到后缀表达式
            postfix.append(list.pop() + " ");
        }
        //返回后缀表达式
        return postfix.toString();
    }

    /**
     * 判断运算符优先级的方法
     *
     * @param op 运算符字符
     * @return 优先级
     */
    private static int prio(char op) {
        int priority = -1;  // 定义一个变量priority用于存储操作符的优先级
        if (op == '*' || op == '/')  // 如果操作符为'*'或'/'，优先级为2
        {
            priority = 2;
        }
        if (op == '+' || op == '-')  // 如果操作符为'+'或'-'
        {
            priority = 1;  // 优先级为1
        }
        if (op == '(')  // 如果操作符为'('
        {
            priority = 0;  // 优先级为0
        }
        return priority;  // 返回操作符的优先级
    }


    public static double postfix2result(String postfix) {
        //创建栈
        Stack<Double> result = new Stack();
        //截取字符串，并转为字符串数组
        String[] tokens = postfix.split(" ");
        //循环并计算
        for (String s : tokens) {
            switch (s) {
                case "+":
                    result.push(result.pop() + result.pop());
                    break;
                case "*":
                    result.push(result.pop() * result.pop());
                    break;
                case "-":
                    result.push(0 - result.pop() + result.pop());
                    break;
                case "/":
                    double b = result.pop();
                    double a = result.pop();
                    result.push(a / b);
                    break;
                default:
                    result.push(Double.parseDouble(s));
            }
        }
        return result.pop();
    }


    public static void main(String[] args) {
        System.out.println("请输入一个算数表达式：");
        Scanner sc=new Scanner(System.in);
        String infix = sc.nextLine();
        String postfix = infix2postfix(infix);
        System.out.println("后缀表达式为："+postfix);
        double result = postfix2result(postfix);
        System.out.println("后缀表达式的运算结果为："+result);
    }
}
